class Solution {  //滑动窗口 + 哈希表(用数组模拟哈希表，全为小写字母，开26空间，映射地址为ch - 'a') O(26n)=O(n)
public:   //异位词，顺序不同，但两串的长度必须相等，且串中的各字符个数均相同
    vector<int> findAnagrams(string s, string p) {
    vector<int> ret;  
    int n1 = s.size(), n2 = p.size(), hash1[26] = {0}, hash2[26] = {0};
    for(auto& e : p)  //将串p的内容全部映射到hash2中
    {
        hash2[e - 'a']++;
    }

    for(int left = 0, right = 0; right < s.size(); right++)
    {
        hash1[s[right] - 'a']++; //进窗口
        if(right - left + 1 > n2)  //判断，用if,因为要维护窗口的大小始终为n2,多一个元素，就会出一个元素
            hash1[s[left++] - 'a']--;  //出窗口
        if(right - left + 1 == n2) //更新结果 从头到尾遍历两个哈希表，看两表是否相等
        {
            int i = 0;
            for(; i < 26; i++)
                if(hash1[i] != hash2[i]) break;  
            if(i == 26)  ret.push_back(left);
        }
    }
    return ret;  //此处更新判断结果，若为字符串，则不可直接遍历哈希表，需要增加个变量count进行维护
    }
};


class Solution {  //滑动窗口 + 哈希表(用数组模拟哈希表，全为小写字母，开26空间，映射地址为ch - 'a') O(n)
public:  //优化版本：优化更新结果的判断条件，直接比较变量值，无需遍历哈希表
    vector<int> findAnagrams(string s, string p) {
    vector<int> ret;
    //count存放的是窗口内"有效字符"的个数，两次更新(<=,进入后、出去前)，一次判断(更新结果)
    int count = 0, n2 = p.size(), hash1[26] = {0}, hash2[26] = {0};
    for(auto& e : p)  //将串p的内容全部映射到hash2中
    {
        hash2[e - 'a']++;
    }

    for(int left = 0, right = 0; right < s.size(); right++)
    {
        int in = s[right] - 'a';
        //进窗口
        //进窗口之后，更新维护count，<=(=,s,p各一个，<,s<p),当前字符为有效字符，count++
        if(++hash1[in] <= hash2[in])  count++;
     
        if(right - left + 1 > n2) //判断
        {   
            int out = s[left] - 'a';
            //出窗口之前，更新维护count，>(=,s,p各一个，<,s<p),当前字符为多余字符，count不更新，反之，count--
            if(hash1[out]-- <= hash2[out]) count--;
            left++;
            //出窗口
        }
        //count数量=n2,说明该窗口内的元素组为异位词
        if(count == n2) ret.push_back(left); //更新结果，此处只需要判断一个变量的值，O(1)
    }
    return ret;
    }
};